home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / ispell40.lha / ispell-4.0 / access.c next >
C/C++ Source or Header  |  1993-05-31  |  14KB  |  738 lines
  1. /* Copyright (C) 1990, 1993 Free Software Foundation, Inc.
  2.  
  3.    This file is part of GNU ISPELL.
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 2, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  18.  
  19. #include <stdio.h>
  20.  
  21. #ifdef HAVE_MALLOC_H
  22. #include <malloc.h>
  23. #endif
  24.  
  25. #include "ispell.h"
  26. #include "hash.h"
  27. #include "build.h"
  28. #include "good.h"
  29.  
  30. #ifdef __STDC__
  31.  
  32. void lexload (FILE *, unsigned long);
  33. int lexsize (void);
  34. void set_bitvec (unsigned char *, unsigned short);
  35. void lexdump (FILE *);
  36.  
  37. #else
  38.  
  39. extern void lexload ();
  40. extern int lexsize ();
  41. extern void lexdump ();
  42. extern void set_bitvec ();
  43.  
  44. #endif
  45.  
  46.  
  47. hash_index hashsize;
  48.  
  49. #ifndef min
  50. #define min(a,b) ((a) < (b) ? (a) : (b))
  51. #endif
  52.  
  53. /* there are 3 tables:
  54.  *
  55.  * all are addressed by unsigned shorts
  56.  *  htbl  hashsize hash table entries
  57.  *  ftbl  hashsize flag entries
  58.  *  stbl  <= 64K bytes of strings
  59.  */
  60. #if iAPX286 && (LARGE_M || HUGE_M)
  61. #define SMALL
  62. #endif
  63. #ifdef SMALL
  64. #define MAXMALLOC 32768
  65.  
  66. struct hash_table_entry **htbls;
  67. /* number of whole hash_table_entries that fit in a table */
  68. #define HTE_PER_TABLE ((MAXMALLOC-1) / sizeof (struct hash_table_entry))
  69. #if 0
  70. struct hash_table_entry *
  71. find_hte (h)
  72.      hash_index h;
  73. {
  74.   unsigned short tbl;
  75.   unsigned short off;
  76.   tbl = h / HTE_PER_TABLE;
  77.   off = h % HTE_PER_TABLE;
  78.  
  79.   return (htbls[tbl] + off);
  80. }
  81.  
  82. #endif
  83. #define H_TO_HTE(h) (htbls[(h)/HTE_PER_TABLE] + ((h)%HTE_PER_TABLE))
  84.  
  85. unsigned short **ftbls;
  86. #define FLAGS_PER_TABLE ((MAXMALLOC-1) / sizeof (unsigned short))
  87. #if 0
  88. unsigned short *
  89. find_flags (h)
  90.      hash_index h;
  91. {
  92.   unsigned short tbl;
  93.   unsigned short off;
  94.   tbl = h / FLAGS_PER_TABLE;
  95.   off = h % FLAGS_PER_TABLE;
  96.   return (ftbls[tbl] + off);
  97. }
  98.  
  99. #endif
  100. #define H_TO_FLAGS(h) (ftbls[(h)/FLAGS_PER_TABLE] + ((h)%FLAGS_PER_TABLE))
  101.  
  102. comp_char **stbls;
  103. #define BYTES_PER_TABLE MAXMALLOC
  104. #if 0
  105. comp_char *
  106. find_string (index)
  107.      str_index index;
  108. {
  109.   unsigned short tbl;
  110.   unsigned short off;
  111.   tbl = index / BYTES_PER_TABLE;
  112.   off = index % BYTES_PER_TABLE;
  113.   return (stbls[tbl] + off);
  114. }
  115.  
  116. #endif
  117. #define INDEX_TO_STRING(index) (stbls[(index)/BYTES_PER_TABLE]+((index)%BYTES_PER_TABLE))
  118. #else
  119. #undef SMALL
  120. struct hash_table_entry *htbl;
  121. unsigned short *ftbl;
  122. comp_char *stbl;
  123.  
  124. #define H_TO_HTE(h) (htbl + (h))
  125. #define H_TO_FLAGS(h) (ftbl + (h))
  126. #define INDEX_TO_STRING(index) (stbl + (index))
  127. #endif
  128.  
  129. #define HASH_NEXT(h) (H_TO_HTE(h)->next)
  130. #define HASH_EMPTY_P(h) (H_TO_HTE(h)->next == HASH_EMPTY)
  131.  
  132. struct hash_table_entry proto_hte;
  133.  
  134. static str_index stbl_size;
  135. static str_index stbl_index;
  136.  
  137. char *
  138. alloc (n)
  139.   unsigned int n;
  140. {
  141.   char *p;
  142.   p = (char *) xcalloc (n, 1);
  143.   return (p);
  144. }
  145.  
  146. void
  147. alloc_tables (hsize, ssize)
  148.   unsigned long hsize, ssize;
  149. {
  150.   hash_index h;
  151. #ifdef SMALL
  152.   unsigned short u, x;
  153.   int i;
  154. #endif
  155.  
  156.   stbl_size = ssize;
  157.   stbl_index = 0;
  158.  
  159. #ifdef SMALL
  160.   u = (ssize + BYTES_PER_TABLE - 1) / BYTES_PER_TABLE;
  161.   stbls = (comp_char **) alloc (u * sizeof (comp_char *));
  162.   u = ssize;
  163.   i = 0;
  164.   while (u != 0)
  165.     {
  166.       x = min (u, BYTES_PER_TABLE);
  167.       stbls[i] = (comp_char *) alloc (x);
  168.       u -= x;
  169.       i++;
  170.     }
  171.   u = (hsize + FLAGS_PER_TABLE - 1) / FLAGS_PER_TABLE;
  172.   ftbls = (unsigned short **) alloc (u * sizeof (unsigned short *));
  173.   u = hsize;
  174.   i = 0;
  175.   while (u != 0)
  176.     {
  177.       x = min (u, FLAGS_PER_TABLE);
  178.       ftbls[i] = (unsigned short *) alloc (x * sizeof (unsigned short));
  179.       u -= x;
  180.       i++;
  181.     }
  182.   u = (hsize + HTE_PER_TABLE - 1) / HTE_PER_TABLE;
  183.   htbls = (struct hash_table_entry **)
  184.     alloc (u * sizeof (struct hash_table_entry *));
  185.   u = hsize;
  186.   i = 0;
  187.   while (u != 0)
  188.     {
  189.       x = min (u, HTE_PER_TABLE);
  190.       htbls[i] = (struct hash_table_entry *)
  191.     alloc (x * sizeof (struct hash_table_entry));
  192.       u -= x;
  193.       i++;
  194.     }
  195. #else
  196.   htbl = (struct hash_table_entry *)
  197.     alloc ((unsigned) (hsize * sizeof proto_hte));
  198.   ftbl = (unsigned short *)
  199.     alloc ((unsigned) (hsize * sizeof (unsigned short)));
  200.   stbl = (comp_char *) alloc ((unsigned) ssize);
  201. #endif
  202.  
  203.   for (h = 0; h < hsize; h++)
  204.     HASH_NEXT (h) = HASH_EMPTY;
  205. }
  206.  
  207. str_index
  208. copy_out_string (s, n)
  209.   comp_char *s;
  210.   int n;
  211. {
  212.   str_index index;
  213.   comp_char *cp;
  214.  
  215. #ifdef SMALL
  216.   unsigned short t1, t2;
  217.   t1 = stbl_index / BYTES_PER_TABLE;
  218.   t2 = (stbl_index + n) / BYTES_PER_TABLE;
  219.   if (t1 != t2)
  220.     stbl_index += BYTES_PER_TABLE - stbl_index % BYTES_PER_TABLE;
  221. #endif
  222.   if (stbl_index + n > stbl_size)
  223.     {
  224.       (void) fprintf (stderr, "string table overflow\n");
  225.       exit (1);
  226.     }
  227.  
  228.   index = stbl_index;
  229.   stbl_index += n;
  230.  
  231.   cp = INDEX_TO_STRING (index);
  232.   while (n--)
  233.     *cp++ = *s++;
  234.  
  235.   return (index);
  236. }
  237.  
  238. /* returns index of end of chain */
  239. hash_index
  240. hash_find_end (index)
  241.      hash_index index;
  242. {
  243.   hash_index next, cur;
  244.  
  245.   for (cur = index, next = HASH_NEXT (index);
  246.        next < HASH_SPECIAL;
  247.        cur = next, next = HASH_NEXT (next))
  248.     ;
  249.   return (cur);
  250. }
  251.  
  252. /* clobbers whatever is there */
  253. void
  254. hash_store (index, htep)
  255.   hash_index index;
  256.   struct hash_table_entry *htep;
  257. {
  258.   *H_TO_HTE (index) = *htep;
  259. }
  260.  
  261. void
  262. hash_retrieve (index, htep)
  263.   hash_index index;
  264.   struct hash_table_entry *htep;
  265. {
  266.   *htep = *H_TO_HTE (index);
  267. }
  268.  
  269. /* updates the next field */
  270. void
  271. hash_set_next (index, new_next)
  272.   hash_index index;
  273.   hash_index new_next;
  274. {
  275.   if (new_next < HASH_SPECIAL && new_next >= hashsize)
  276.     {
  277.       (void) fprintf (stderr, "bad index to set_next %x\n", new_next);
  278.       exit (1);
  279.     }
  280.   HASH_NEXT (index) = new_next;
  281. }
  282.  
  283. int
  284. hash_emptyp (h)
  285.   hash_index h;
  286. {
  287.   return (HASH_EMPTY_P (h));
  288. }
  289.  
  290. void
  291. store_flags (hindex, flags)
  292.      hash_index hindex;
  293.      unsigned short flags;
  294. {
  295.   *H_TO_FLAGS (hindex) = flags;
  296. }
  297.  
  298.  
  299. int
  300. hash_init (name)
  301.   char *name;
  302. {
  303.   FILE *in;
  304.   struct hash_header hhdr;
  305.   int i, j, c, bit;
  306. #ifdef SMALL
  307.   hash_index h;
  308.   unsigned short flags;
  309.   unsigned short u;
  310.   unsigned short x;
  311.   struct hash_table_entry hte;
  312.   long l;
  313. #endif
  314. #ifdef MSDOS
  315.   if ((in = fopen (name, "rb")) == NULL)
  316.     return (-1);
  317. #else
  318.   if ((in = fopen (name, "r")) == NULL)
  319.     return (-1);
  320. #endif
  321.   if (fread ((char *) &hhdr, (int) sizeof hhdr, 1, in) != 1)
  322.     goto bad;
  323.  
  324.   if (hhdr.magic != HMAGIC)
  325.     goto bad;
  326.   if (hhdr.version != VERSION)
  327.     {
  328.       (void) fprintf (stderr,
  329.               "ispell: wanted dict version %d, got %d\n",
  330.               VERSION, hhdr.version);
  331.       goto bad;
  332.     }
  333.  
  334.   for (i = 0; i < 32; i++)
  335.     {
  336.       for (j = 0, bit = 1; j < 8; j++, bit <<= 1)
  337.     {
  338.       if (hhdr.used[i] & bit)
  339.         {
  340.           c = i * 8 + j;
  341.           if (near_map[c] == 0)
  342.         near_miss_letters[nnear_miss_letters++]
  343.           = c;
  344.         }
  345.     }
  346.     }
  347.  
  348.   lexload (in, hhdr.lexletters);
  349.  
  350.   if (ftell (in) != sizeof hhdr + hhdr.lexsize)
  351.     {
  352.       (void) fprintf (stderr, "bad dictionary file\n");
  353.       exit (1);
  354.     }
  355.  
  356.   hashsize = hhdr.hashsize;
  357.   alloc_tables (hhdr.hashsize, hhdr.stblsize);
  358.  
  359. #ifdef SMALL
  360.   l = (long) hashsize *sizeof hte;
  361.   i = 0;
  362.   while (l != 0)
  363.     {
  364.       x = min (l, HTE_PER_TABLE * sizeof hte);
  365.       if (fread ((char *) htbls[i], 1, (int) x, in) != (int) x)
  366.     goto bad;
  367.       l -= x;
  368.       i++;
  369.     }
  370.   l = (long) hashsize *sizeof flags;
  371.   i = 0;
  372.   while (l != 0)
  373.     {
  374.       x = min (l, FLAGS_PER_TABLE * sizeof flags);
  375.       if (fread ((char *) ftbls[i], 1, (int) x, in) != (int) x)
  376.     goto bad;
  377.       l -= x;
  378.       i++;
  379.     }
  380.   u = stbl_size;
  381.   i = 0;
  382.   while (u != 0)
  383.     {
  384.       x = min (u, BYTES_PER_TABLE);
  385.       if (fread ((char *) stbls[i], 1, (int) x, in) != (int) x)
  386.     goto bad;
  387.       u -= x;
  388.       i++;
  389.     }
  390. #else
  391.   if (fread ((char *) htbl, (int) sizeof *htbl, (int) hashsize, in) !=
  392.       (int) hashsize)
  393.     goto bad;
  394.   if (fread ((char *) ftbl, (int) sizeof *ftbl, (int) hashsize, in) !=
  395.       (int) hashsize)
  396.     goto bad;
  397.   if (fread ((char *) stbl, 1, (int) stbl_size, in) != (int) stbl_size)
  398.     goto bad;
  399. #endif
  400.   (void) fclose (in);
  401.   return (0);
  402. bad:
  403.   (void) fclose (in);
  404.   return (-1);
  405. }
  406.  
  407. #define NHASHSTAT 100
  408. long hashstat[NHASHSTAT];
  409.  
  410. void
  411. dumphashstat (NOARGS)
  412. {
  413.   int i;
  414.  
  415.   for (i = 0; i < NHASHSTAT; i++)
  416.     if (hashstat[i])
  417.       (void) printf ("%d %ld\n", i, hashstat[i]);
  418. }
  419.  
  420.  
  421. int
  422. hashchainlen (h)
  423.   hash_index h;
  424. {
  425.   struct hash_table_entry *rh;
  426.   int i = 0;
  427.  
  428.   for (h = h % hashsize;
  429.        h < HASH_SPECIAL;
  430.        h = rh->next)
  431.     {
  432.       rh = H_TO_HTE (h);
  433.       i++;
  434.     }
  435.   if (i >= NHASHSTAT)
  436.     i = NHASHSTAT - 1;
  437.   return (i);
  438. }
  439.  
  440.  
  441. void
  442. prhashchain ()
  443. {
  444.   hash_index h;
  445.   int i;
  446.  
  447.   for (i = 0; i < NHASHSTAT; i++)
  448.     hashstat[i] = 0;
  449.  
  450.   for (h = 0; h < hashsize; h++)
  451.     hashstat[hashchainlen (h)]++;
  452.  
  453.   dumphashstat ();
  454. }
  455.  
  456. /*
  457.  * returns 0 for not found, otherwise, the index
  458.  */
  459.  
  460. hash_index
  461. hash_lookup (string, alen)
  462.   comp_char *string;
  463.   int alen;
  464. {
  465.   register int n;
  466.   register comp_char *p;
  467.   register comp_char *hp;
  468.   register int len;
  469.   register struct hash_table_entry *rh;
  470.   register hash_index h;
  471.  
  472.   len = alen;
  473.  
  474.   if (len <= sizeof proto_hte.u.s.data)
  475.     {
  476.       for (h = hash ((char *) string) % hashsize;
  477.        h < HASH_SPECIAL;
  478.        h = rh->next)
  479.     {
  480.       rh = H_TO_HTE (h);
  481.       /* should do if (rh->next == HASH_EMPTY) continue;
  482.              * here, but since we know that the rest of the
  483.              * entry will be zero, it can't match anyway, and
  484.              * we get out of the loop next time anyway */
  485.       if (!rh->u.l.short_flag)
  486.         continue;
  487.       hp = rh->u.s.data;
  488.       p = string;
  489.       for (n = len; n > 0; --n)
  490.         if (*p++ != *hp++)
  491.           goto fail1;
  492.       if (len < sizeof proto_hte.u.s.data && *hp != 0)
  493.         goto fail1;
  494.       return (h);
  495.     fail1:;
  496.     }
  497.       return (0);
  498.     }
  499.   else
  500.     {
  501.       for (h = hash ((char *) string) % hashsize;
  502.        h < HASH_SPECIAL;
  503.        h = rh->next)
  504.     {
  505.       rh = H_TO_HTE (h);
  506.       if (rh->u.l.short_flag)
  507.         continue;
  508.       if ((int) rh->u.l.len != len)
  509.         continue;
  510.       hp = rh->u.l.data;
  511.       p = string;
  512.       for (n = sizeof proto_hte.u.l.data; n > 0; --n)
  513.         if (*p++ != *hp++)
  514.           goto fail2;
  515.       hp = INDEX_TO_STRING (rh->u.l.sindex);
  516.       for (n = len - sizeof proto_hte.u.l.data; n > 0; --n)
  517.         if (*p++ != *hp++)
  518.           goto fail2;
  519.       return (h);
  520.     fail2:;
  521.     }
  522.       return (0);
  523.     }
  524. }
  525.  
  526. unsigned short
  527. get_flags (hindex)
  528.      hash_index hindex;
  529. {
  530.   return (*H_TO_FLAGS (hindex));
  531. }
  532.  
  533. unsigned char *freqletters;
  534.  
  535.  
  536. void
  537. hash_write (f)
  538.   FILE *f;
  539. {
  540.   struct hash_header hhdr;
  541.   extern int lexletters;
  542.   int i;
  543.   unsigned char *p;
  544. #ifdef SMALL
  545.   unsigned short h;
  546.   unsigned short x;
  547.   struct hash_table_entry hte;
  548.   unsigned short flags;
  549. #endif
  550.  
  551.   hhdr.magic = HMAGIC;
  552.   hhdr.version = VERSION;
  553.   hhdr.lexletters = lexletters;
  554.   hhdr.lexsize = lexsize ();
  555.   hhdr.hashsize = hashsize;
  556.   hhdr.stblsize = stbl_index;
  557.  
  558.   for (i = 0; i < 32; i++)
  559.     hhdr.used[i] = 0;
  560.  
  561.   for (p = freqletters; *p; p++)
  562.     set_bitvec (hhdr.used, *p);
  563.  
  564.   if (fwrite ((char *) &hhdr, (int) sizeof hhdr, 1, f) != 1)
  565.     goto bad;
  566.  
  567.   lexdump (f);
  568.  
  569.   if (ftell (f) != sizeof hhdr + hhdr.lexsize)
  570.     {
  571.       (void) fprintf (stderr, "lexdump used wrong number of bytes\n");
  572.       exit (1);
  573.     }
  574.  
  575. #ifdef SMALL
  576.   for (h = 0; h < hashsize; h++)
  577.     {
  578.       hash_retrieve (h, &hte);
  579.       if (fwrite ((char *) &hte, (int) sizeof hte, 1, f) != 1)
  580.     goto bad;
  581.     }
  582.   for (h = 0; h < hashsize; h++)
  583.     {
  584.       flags = get_flags (h);
  585.       if (fwrite ((char *) &flags, (int) sizeof (flags), 1, f) != 1)
  586.     goto bad;
  587.     }
  588.   h = stbl_index;
  589.   i = 0;
  590.   while (h != 0)
  591.     {
  592.       x = min (h, BYTES_PER_TABLE);
  593.       if (fwrite ((char *) stbls[i], (int) x, 1, f) != 1)
  594.     goto bad;
  595.       h -= x;
  596.       i++;
  597.     }
  598. #else
  599.   if (fwrite ((char *) htbl, (int) sizeof htbl[0], (int) hashsize, f) !=
  600.       (int) hashsize)
  601.     goto bad;
  602.   if (fwrite ((char *) ftbl, (int) sizeof ftbl[0], (int) hashsize, f) !=
  603.       (int) hashsize)
  604.     goto bad;
  605.   if (fwrite ((char *) stbl, 1, (int) stbl_index, f) != (int) stbl_index)
  606.     goto bad;
  607. #endif
  608.   return;
  609. bad:
  610.   (void) fprintf (stderr, "error writing hash table\n");
  611.   exit (1);
  612.   /* NOTREACHED */
  613. }
  614.  
  615.  
  616. void
  617. hash_awrite (out)
  618.   FILE *out;
  619. {
  620.   struct hash_table_entry hte;
  621.   hash_index h;
  622.   char *entry;
  623.  
  624.   for (h = 1; h < hashsize; h++)
  625.     {
  626.       hash_retrieve (h, &hte);
  627.       if (hte.next < HASH_SPECIAL ||
  628.       hte.next == HASH_END)
  629.     {
  630.       entry = htetostr (&hte, h);
  631.       if (*entry && *entry != '/')
  632.         {
  633.           fputs (entry, out);
  634.           putc ('\n', out);
  635.         }
  636.     }
  637.     }
  638. }
  639.  
  640.  
  641. void
  642. hash_ewrite (out)
  643.   FILE *out;
  644. {
  645.   struct hash_table_entry hte;
  646.   hash_index h;
  647.   char *entry;
  648.   int n, i;
  649.  
  650.   for (h = 1; h < hashsize; h++)
  651.     {
  652.       hash_retrieve (h, &hte);
  653.       if (hte.next < HASH_SPECIAL ||
  654.       hte.next == HASH_END)
  655.     {
  656.       entry = htetostr (&hte, h);
  657.       n = expand (entry);
  658.       for (i = 0; i < n; i++)
  659.         {
  660.           if (words[i] == (char *) NULL)
  661.         break;
  662.           (void) fputs (words[i], out);
  663.           (void) putc ('\n', out);
  664.         }
  665.     }
  666.     }
  667. }
  668.  
  669. char *
  670. htetostr (htep, h)
  671.   struct hash_table_entry *htep;
  672.   hash_index h;
  673. {
  674.   comp_char *p;
  675.   int i;
  676.  
  677.   int len;
  678.   unsigned short bit, f;
  679.   static char hstr[100];
  680.   char *outp, *q;
  681.  
  682.   outp = hstr;
  683.  
  684.   if (htep->u.l.short_flag)
  685.     {
  686.       for (p = htep->u.s.data, i = 0;
  687.        *p && i < sizeof proto_hte.u.s.data;
  688.        p++, i++)
  689.     {
  690.       q = lexdecode[*p];
  691.       while (*q)
  692.         *outp++ = *q++;
  693.     }
  694.     }
  695.   else if (*(p = htep->u.l.data) && (len = htep->u.l.len))
  696.     {
  697.       for (i = 0;
  698.        i < sizeof proto_hte.u.l.data;
  699.        p++, i++)
  700.     {
  701.       q = lexdecode[*p];
  702.       while (*q)
  703.         *outp++ = *q++;
  704.     }
  705.       len -= sizeof proto_hte.u.l.data;
  706.       p = INDEX_TO_STRING (htep->u.l.sindex);
  707.       for (i = 0; i < len; i++)
  708.     {
  709.       q = lexdecode[*p];
  710.       while (*q)
  711.         *outp++ = *q++;
  712.       p++;
  713.     }
  714.     }
  715.   f = get_flags (h);
  716.   for (i = 0, bit = 1; i < 16; i++, bit <<= 1)
  717.     {
  718.       if (f & bit)
  719.     {
  720.       *outp++ = '/';
  721.       *outp++ = flag_char (i);
  722.     }
  723.     }
  724.   *outp = 0;
  725.   return (hstr);
  726. }
  727.  
  728. void
  729. set_bitvec (bitvec, n)
  730.   unsigned char *bitvec;
  731.   unsigned short n;
  732. {
  733.   static unsigned char bittbl[] =
  734.   {1, 2, 4, 8, 0x10, 0x20, 0x40, 0x80};
  735.  
  736.   bitvec[n >> 3] |= bittbl[n & 7];
  737. }
  738.